package com.sfx.算法专题.链表.链表基础构造;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-07-29
 * Time: 14:06
 */


public class MySingleLinkedList {
    //构造链表结点
    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }
    }

    private static ListNode head;
    private static final Random random = new Random();

    //1.创建链表-->创建右5个节点组成的链表
    public static void createLinkedList() {
        ListNode prev = null;
        for (int i = 1; i <= 5; ++i) {
            if (head == null) {
                head = new ListNode(random.nextInt(100) + 1);
                prev = head;
            } else {
                assert prev != null;
                prev.next = new ListNode(random.nextInt(100) + 1);
                prev = prev.next;
            }
        }
    }

    //2.遍历链表,返回链表长度
    public static int length(ListNode head) {
        ListNode cur = head;
        int cnt = 0;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    //3.打印链表
    public static void print(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //4.链表插入
    //4.1头插
    public static void addFirst(int val) {
        if (head == null) {
            head = new ListNode(val);
        }
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

    //4.2尾插
    public static void addLast(int val) {
        if (head == null) {
            head = new ListNode(val);
        }
        //找到尾部
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = new ListNode(val);
    }

    //4.3指定位置插入
    public static void add(int val, int index) {
        //1.判断index是否合法
        if (index < 0 || index > length(head)) {
            throw new RuntimeException("index不合法");
        }
        //2.index为特殊位置
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == length(head)) {
            addLast(val);
            return;
        }
        ListNode cur = head;
        ListNode prev = null;
        //3.走index步,插入进去
        for (int i = 0; i < index; ++i) {
            prev = cur;
            cur = cur.next;
        }
        //0 1 2 3 4
        ListNode node = new ListNode(val);
        node.next = cur.next;
        prev.next = node;
    }

    //5.链表删除
    //5.1头删
    public static void removeFirst() {
        if (head == null) throw new RuntimeException("头结点为空");
        head = head.next;
    }

    //5.2尾删
    public static void removeLast() {
        if (head == null) throw new RuntimeException("头结点为空");
        ListNode cur = head;
        ListNode prev = null;
        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
        if (prev == null) {
            head = null;
            return;
        }
        prev.next = null;
    }

    //5.3指定位置删除
    public static void remove(int index) {
        if (head == null) throw new RuntimeException("头结点为空");
        if (index < 0 || index >= length(head)) throw new RuntimeException("index不合法");
        if (index == 0) {
            removeFirst();
            return;
        }
        if (index == length(head) - 1) {
            removeLast();
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index - 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }

    public static void main(String[] args) {
        createLinkedList();
        print(head);
        addFirst(100);
        print(head);
        addLast(100);
        print(head);
        add(8888, 4);
        print(head);
        removeFirst();
        print(head);
        removeLast();
        print(head);
        remove(1);
        print(head);
        remove(1);
        print(head);
        remove(1);
        print(head);
        remove(1);
        print(head);
        remove(0);
        print(head);
    }
}